package practise.alogrithm.hundredInterviewQuestions;

import practise.alogrithm.hundredInterviewQuestions.Utils.LinkedListBuilder;
import practise.alogrithm.hundredInterviewQuestions.Utils.ListNode;
import sun.awt.image.ImageWatched;

/**
 * Created by richard on 6/3/14.
 */
public class ReverseLinkedList {

    public static ListNode execute(ListNode head){
        if(head.getNext()==null){
            return head;
        }
        ListNode nextNode = head.getNext();
        ListNode newHead = execute(head.getNext());
        nextNode.setNext(head);
        head.setNext(null);
        return newHead;
    }
    public static ListNode reverse(ListNode head){
       ListNode h = new ListNode();
       reverse(head,h);// need to head to get back the new header
        head.setNext(null);//need set the new tail point to null
        return h.getNext();
    }

    private static ListNode reverse(ListNode node, ListNode head){
        if(node.getNext()==null){
            head.setNext(node);
            return node;
        }
        reverse(node.getNext(),head).setNext(node);
        return node;
    }

    public static void main(String[] args){
        ListNode listNode = reverse(LinkedListBuilder.buildLinkedListFromArray(new int[]{1,2,3,4,5,6,7,8,9}));
        System.out.println("Result:");
        while(listNode.getNext()!=null){
            System.out.print(listNode.getValue()+",");
            listNode=listNode.getNext();
        }
        System.out.print(listNode.getValue());

        System.out.println();
        listNode = execute(LinkedListBuilder.buildLinkedListFromArray(new int[]{1,2,3,4,5,6,7,8,9}));
        System.out.println("Result:");
        while(listNode.getNext()!=null){
            System.out.print(listNode.getValue()+",");
            listNode=listNode.getNext();
        }
        System.out.print(listNode.getValue());
    }
}
